package com.leet.tree;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class PathSum {
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null) return 0;
        int ans = 0;
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode head = q.poll();
                int curSum = helper(head, targetSum, 0, 0);
                ans += curSum;
                if(root.left != null) q.offer(root.left);
                if (root.right != null) q.offer(root.right);
            }
        }
        return ans;
    }
    public int helper(TreeNode root, int targetSum,int currentSum,int cntAns) {
        if(root == null) return 0;
        currentSum += root.val;
        if(currentSum == targetSum) cntAns++;
        helper(root.left,targetSum,currentSum,cntAns);
        helper(root.right,targetSum,currentSum,cntAns);
        return cntAns;
    }

    public static void main(String[] args) {
        PathSum pathSum = new PathSum();
        TreeNode root =  new TreeNode(-1);
        root.right = new TreeNode(2);
        root.left = null;
        int ans = pathSum.pathSum(root, -1);
        System.out.println(ans);
    }
}
